package org.algorithm.biubiu.wheel_1.回溯算法;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 * 46. 全排列
 * 链接：https://leetcode-cn.com/problems/permutations/
 */
public class $4月24日$全排列 {


    List<List<Integer>> res2 = new ArrayList();
    int[] nums2;
    public List<List<Integer>> permute(int[] nums) {
        this.nums2 = nums;

        boolean[] use = new boolean[nums.length];
        backTrack(use);
        return res2;
    }


    List<Integer> cur2 = new ArrayList();
    public void backTrack(boolean[] use){
        if(cur2.size()== nums2.length){
            res2.add(new ArrayList(cur2));
        }
        // 每次在0开始 就需要重新判断是否使用过  ？？？？ 那么可以 每次由下一个元素开始  step2
        for(int i = 0; i< nums2.length; i++){
            if(use[i]==true) continue;
            //剪纸
            cur2.add(nums2[i]);
            use[i] = true;
            backTrack(use);
            use[i] = false;
            cur2.remove(cur2.size()-1);
        }

    }


    // ------------------------------------------------two----------------------------------------------------------
    List<List<Integer>> res =new ArrayList();
    int[] arr;
    public List<List<Integer>> permute2(int[] nums) {

        this.arr = nums;
        backTrack(0);
        return res;
    }

    List<Integer> cur = new ArrayList();

    public void backTrack(int step){

        if(step==arr.length){
            res.add(toList(arr));
            return ;
        }

        for(int i=step;i<arr.length;i++){
            swap(step,i);
            backTrack(step+1);
            swap(i,step);
        }
    }


    public void swap(int step,int i){
        if(step==i) return ;
        System.out.println(step +"---->" + i);
        int tmp;
        tmp = arr[step];
        arr[step] = arr[i];
        arr[i] = tmp;
    }

    public List toList(int[] arr){
        List res = new ArrayList();
        for(int e: arr){
            res.add(e);
        }
        return res;

    }





}
